package Leetcode.每日一题;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * @ClassName 消灭怪物数量
 * @since: 2023/9/4 09:42
 * @auth: kirito
 * @description:
 * 你正在玩一款电子游戏，在游戏中你需要保护城市免受怪物侵袭。给你一个 下标从 0 开始 且长度为 n 的整数数组 dist ，其中 dist[i] 是第 i 个怪物与城市的 初始距离（单位：米）。
 *
 * 怪物以 恒定 的速度走向城市。给你一个长度为 n 的整数数组 speed 表示每个怪物的速度，其中 speed[i] 是第 i 个怪物的速度（单位：米/分）。
 *
 * 怪物从 第 0 分钟 时开始移动。你有一把武器，并可以 选择 在每一分钟的开始时使用，包括第 0 分钟。但是你无法在一分钟的中间使用武器。这种武器威力惊人，一次可以消灭任一还活着的怪物。
 *
 * 一旦任一怪物到达城市，你就输掉了这场游戏。如果某个怪物 恰 在某一分钟开始时到达城市，这会被视为 输掉 游戏，在你可以使用武器之前，游戏就会结束。
 *
 * 返回在你输掉游戏前可以消灭的怪物的 最大 数量。如果你可以在所有怪物到达城市前将它们全部消灭，返回  n 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：dist = [1,3,4], speed = [1,1,1]
 * 输出：3
 * 解释：
 * 第 0 分钟开始时，怪物的距离是 [1,3,4]，你消灭了第一个怪物。
 * 第 1 分钟开始时，怪物的距离是 [X,2,3]，你没有消灭任何怪物。
 * 第 2 分钟开始时，怪物的距离是 [X,1,2]，你消灭了第二个怪物。
 * 第 3 分钟开始时，怪物的距离是 [X,X,1]，你消灭了第三个怪物。
 * 所有 3 个怪物都可以被消灭。
 * 示例 2：
 *
 * 输入：dist = [1,1,2,3], speed = [1,1,1,1]
 * 输出：1
 * 解释：
 * 第 0 分钟开始时，怪物的距离是 [1,1,2,3]，你消灭了第一个怪物。
 * 第 1 分钟开始时，怪物的距离是 [X,0,1,2]，你输掉了游戏。
 * 你只能消灭 1 个怪物
 **/
public class 消灭怪物数量 {

    public int eliminateMaximum(int[] dist, int[] speed) {
        int n = dist.length;  // 数组长度
        int[] res = new int[n];  // 存储每个怪兽到达终点所需的时间

        // 计算每个怪兽到达终点所需的时间
        for (int i = 0; i < n; i++) {
            //保证向上取整
            res[i] = (dist[i] - 1) / speed[i] + 1;
        }

        Arrays.sort(res);  // 将到达终点所需时间按升序排序

        // 检查是否有怪兽在到达终点之前被消灭
        for (int i = 0; i < n; i++) {
            if (res[i] <= 0) {
                return i;  // 返回首个到达终点时间小于等于0的怪兽的索引
            }
        }

        return n;  // 如果所有怪兽都能在到达终点之前被消灭，则返回怪兽的总数
    }

//    假设有两个怪兽的距离和速度分别为：
//
//    dist = [10, 5]
//    speed = [2, 3]
//
//    我们来计算第一个怪兽到达终点所需的时间：
//
//    dist[0] = 10，怪兽离起点的距离为 10
//            (dist[0] - 1) = (10 - 1) = 9，从终点反推，到达终点需要走过的距离为 9
//    speed[0] = 2，怪兽的移动速度为 2
//            (dist[0] - 1) / speed[0] = 9 / 2 = 4，怪兽到达终点所需的时间为 4
//            + 1，考虑到最后一步到达终点的时间，总时间为 4 + 1 = 5
//
//    所以，第一个怪兽到达终点所需的时间为 5。
//
//    现在我们计算第二个怪兽到达终点所需的时间：
//
//    dist[1] = 5，怪兽离起点的距离为 5
//            (dist[1] - 1) = (5 - 1) = 4，从终点反推，到达终点需要走过的距离为 4
//    speed[1] = 3，怪兽的移动速度为 3
//            (dist[1] - 1) / speed[1] = 4 / 3 ≈ 1.33，怪兽到达终点所需的时间为约 1.33
//            + 1，考虑到最后一步到达终点的时间，总时间为约 1.33 + 1 ≈ 2.33，但由于整数除法的特性，结果将被截断为整数 2
//
//    所以，第二个怪兽到达终点所需的时间为 2。
//
//    将这些时间值存储在 res 数组中，结果为：
//
//    res = [5, 2]
}
